/**
 * @file     orangeRotting.js
 * @brief    [994. 腐烂的橘子](https://leetcode.cn/problems/rotting-oranges/)
 * @author   Zhu
 * @date     2024-12-02 14:30
 */

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function (grid) {
    const m = grid.length;
    const n = grid[0].length;

    const queue = [];
    const time = new Map();

    let freshCount = 0;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] == 2) {
                queue.push([i, j]);
                time.set([i, j].join(), 0);
            } else if (grid[i][j] == 1) {
                freshCount++;
            }
        }
    }

    let ans = 0;
    const dir = [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1],
    ];
    while (queue.length && freshCount) {
        const [i, j] = queue.shift();
        const nextTime = time.get([i, j].join()) + 1;
        for (let k = 0; k < 4; k++) {
            const [a, b] = dir[k];
            const ii = i + a,
                jj = j + b;
            if (ii >= 0 && jj >= 0 && ii < m && jj < n && grid[ii][jj] === 1) {
                queue.push([ii, jj]);
                time.set([ii, jj].join(), nextTime);
                grid[ii][jj] = 2;
                freshCount--;
                ans = nextTime;
            }
        }
    }

    if (freshCount > 0) return -1;
    return ans;
};
